#define _CRT_SECURE_NO_WARNINGS

//#include<stdio.h>
//#include<math.h>
//#include <limits.h>
//int n;
//int num[10][2];
//int min = INT_MAX;
//int min_ = 0;
//void process(int acid, int bitter,int idx,int count)
//{
//	if (idx == n)
//	{
//		if (count > 0)
//		{
//			min_ = abs(acid - bitter);
//			if (min > min_)
//			{
//				min = min_;
//			}
//		}
//		return;
//	}
//	process(acid * num[idx][0], bitter + num[idx][1], idx + 1,count+1);
//	process(acid, bitter, idx + 1,count);
//}
//int main()
//{
//	scanf("%d",&n);
//	for (int i = 0; i < n; i++)
//	{
//
//		scanf("%d %d", &num[i][0], &num[i][1]);
//	}
//	process(1,0,0,0);
//	printf("%d",min);
//	return 0;
//}

//#include<stdio.h>
//#include<stdbool.h>
//int sx, sy, ex, ey;
//int count = 0;
//bool mark[10][10];
//int maze[10][10];
//int dx[4] = {1,-1,0,0};
//int n, m, t;
//int dy[4] = {0, 0, 1, -1};
//bool isvalid(int x, int y)
//{
//	return x >= 1 && x <= n && y >=1 && y <= m && !maze[x][y] && !mark[x][y];
//}
//void dfs(int sx, int sy)
//{
//	if (sx == ex && sy == ey)
//	{
//		count++;
//		return;
//	}
//	mark[sx][sy] = true;
//	for (int i = 0; i < 4; i++)
//	{
//		int nx = sx + dx[i];
//		int ny = sy + dy[i];
//		if (isvalid(nx, ny))
//		{
//			dfs(nx, ny);
//		}
//	}
//	mark[sx][sy] = false;
//}
//int main()
//{
//	scanf("%d %d %d", &n, &m, &t);
//	scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
//	for (int i = 1; i < n; i++)
//	{
//		for (int j = 1; j < m; j++)
//		{
//			maze[i][j] = 0;
//			mark[i][j] = false;
//		}
//	}
//	for (int i = 0; i < t; i++)
//	{
//		int x, y;
//		scanf("%d %d", &x, &y);
//		maze[x][y] = 1;
//	}
//	dfs(sx, sy);
//	printf("%d",count);
//	return 0;
//}


//#include<stdio.h>
//#include<math.h>
//int main()
//{
//	long long int n;
//	scanf("%lld", &n);
//	int left = 0;
//	long long int right =(long long) pow((double)n, 1. / 3)+1;
//	int mid = 0;
//	if (n == 1)
//	{
//		printf("1");
//		return 0;
//	}
//	while (left <= right)
//	{
//		mid = left + (right - left) / 2;
//		if (mid == (n / (mid * 1.0) )/ mid)
//		{
//			printf("%d", mid);
//			return 0;
//		}
//		if (mid > (n / (mid * 1.0)) / mid)
//		{
//			right = mid - 1;
//		}
//		else if (mid < (n / (mid * 1.0)) / mid)
//		{
//			left =mid + 1;
//		}
//	}
//	printf("%d\n",right);
//	return 0;
//}

//#include <stdio.h>
//#include <string.h>
//char* process(char* str,char* sub) 
//{
//    char result[100];  
//    char* p = str;           
//    char* pos;                
//    int subLen = strlen(sub);   
//    result[0] = '\0';
//    while ((pos = strstr(p, sub)) != NULL) 
//    {
//        strncat(result, p, pos - p);
//        p = pos + subLen;
//    }
//    strcat(result, p);
//    return result;
//}
//int main() {
//    char str[100], sub[100];
//    scanf("%s %s", sub,str);
//    char* result =process(str, sub);
//    printf("%s\n", result);
//    return 0;
//}


//#include <stdio.h>
//#include <string.h>
//char*process(char* str, const char* sub)
//{
//    static char result[100];  
//    char* p = str;            
//    char* pos;                
//    int len = strlen(sub); 
//    result[0] = '\0';
//    while ((pos = strstr(p, sub)) != NULL) {
//        strncat(result, p, pos - p);
//        p = pos +len;
//    }
//    strcat(result, p);
//    return result;
//}
//int main() {
//    char sub[100], str[100];
//    scanf("%s", sub);
//    getchar();
//    scanf("%s", str);
//    char* result =process(str, sub);
//    printf("%s\n", result);
//    return 0;
//}

//#include <stdio.h>
//#include <string.h>
//char* process(char* str, const char* sub) 
//{
//    static char result[100]; 
//    char* p = str;          
//    char* pos=NULL;              
//    int len = strlen(sub); 
//    result[0] = '\0';
//    while ((pos = strstr(p, sub)) != NULL)
//    {
//        strncat(result, p, pos - p);
//        p = pos +len;
//    }
//    strcat(result, p);
//    return result;
//}
//int main() {
//    char sub[100], str[100];
//    scanf("%s %s", sub,str);
//    char* output = process(str, sub);
//    printf("%s\n", output);
//    return 0;
//}
//


